package leetcode.array;

/**
 * @author Cheng Jun
 * Description: 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-sudoku
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/23 23:50
 * 面试题 二刷 经典之典中典
 */
public class isValidSudoku {

    // [["5","3",".",".","7",".",".",".","."]
    // ,["6",".",".","1","9","5",".",".","."]
    // ,[".","9","8",".",".",".",".","6","."]
    // ,["8",".",".",".","6",".",".",".","3"]
    // ,["4",".",".","8",".","3",".",".","1"]
    // ,["7",".",".",".","2",".",".",".","6"]
    // ,[".","6",".",".",".",".","2","8","."]
    // ,[".",".",".","4","1","9",".",".","5"]
    // ,[".",".",".",".","8",".",".","7","9"]]

    // 思路：模式识别题目
    // 每行、每列、每个3x3格子 都必须满足 数字唯一性
    // 对于 char 类型，一般用 数组解题，而不是用Map，因为数组的空间消耗小，且可以根据 char字符计算出位置。
    // 对于 行，创建 int[9][9] 二层循环，外层行内层列，把数字出现的次数 放到对应列上，然后看列上的次数是否对于1. 判断列是同理。
    // 对于 3x3格子，需要一点空间想象力。将平面的 9 个 3x3小格子看做 9个点，每个点往上长出九个点。所以创建数组 int[3][3][9]
    // 其中 [3][3] 表示 平面的点， [9]表示 每个格子有九个位置，分别放置1-9数字
    static public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] cols = new int[9][9];
        int[][][] grids = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int index = board[i][j] - '0' - 1;
                    // 同行的数字 规整到相应位置
                    rows[i][index]++;
                    // 同列的数字 规整到相应位置
                    cols[index][j]++;
                    grids[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || cols[index][j] > 1 || grids[i / 3][j / 3][index] > 1){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
